Uczenie maszynowe

Lista 4: Algorytmy grupowania danych

Autor: Patryk Rygiel (250080)
GitHub: https://github.com/PatRyg99/ML-PWR-2022

IRIS

1. K-means vs PAM (domyślne parametry)

W ramach tej listy będziemy się zajmować algorytmami grupowania K-means oraz PAM (ang. partitioning around medoids).

Proces działania algorytmu K-means:

  1. Wybieramy losowo zadaną ilość centroidów początkowych $K$, które reprezentują osobne klastry
  2. Dla każdego elementu $x$ w zbiorze liczymy jego odległość do każdego z centroidów i przypisujemy do klastra, do którego znajduje się na bliżej.
  3. Wyznaczamy ponownie lokalizacje centroidów poprzez wyliczenie średniej klastra.
  4. Powtarzamy kroki 2 i 3, aż do osiągnięcia kryterium stopu - zbiegnięcie algorytmu (brak zmian w iteracjach), maksymalna ilość iteracji

Algorytm PAM różni się od K-means tylko krokiem 3. Wartości centroidów są wyznaczane poprzez wyznaczenie centralnego obiektu w klastrze - takiego dla którego odległość dla wszystkich innych elementów klastra jest minimalna. W takiej sytuacji takowy obiekt nazywamy medoidem, zamiast centoidem.

Dla każdej z metod klasteryzacji wykonane zostało 5 prób - w każdej początkowe centroidy są wybierane losowo.

Analizując przykładowe klasteryzacje, możemy zauważyć, że algorytm PAM osiąga wizualnie lepsze i bardziej stabilne rezultaty niż K-means. Dla przykładu 3 widzimy, że K-means połączył klastry Iris-versicolor oraz Iris-virginica w jeden klaster i wyznaczył nowy klaster w obrębie klasy Iris-setosa.

Ewidentnie K-means jest wrażliwy na wybór początkowych centroidów, PAM wydaje się być mniej wrażliwy. Prawdopodobnie powodem takiego zachowania jest fakt, że K-means jest bardziej wrażliwy na outliery ze względu na branie średniej, a nie elementu centralnego jako reprezentanta grupującego dla klastra.

2. Badanie klasteryzacji dla różnych ustawień parametrów początkowych

Do badania jakości grupowania przez oba algorytmy klasteryzacji będziemy używać dwóch miar, jednej nadzorowanej purity i drugiej nienadzorowanej silhouette.

Purity - (nadzorowana) dla każdego klastra przypisujemy mu klasę na podstawie najczęściej występującej w nim klasy. Następnie sumujemy ile dla każdego klastra dla ile jego elementów ich klasa pokrywa się z klasą przypisaną. Ostatecznie dzielimy sumę przez ilość wszystkich elementów co w rezultacie daje nam wartości z przedziału od 0 do 1 - gdzie im większa wartość tym lepiej.

Silhouette - (nienadzorowana) miara na ile obiekt jest podobny do swojego klastra w porównaniu do innych klastrów. Przyjmuje wartości od -1 do 1 i większa wartość świadczy o lepszym dopasowaniu - odpowiednia konfiguracja klastrów. Miarę można liczyć przy użyciu różnych metryk odległości.

2.1 K-means

W ramach badanie algorytmu K-means skupimy się na 4 parametrach:

2.1.1 Badanie maksymalnej ilości iteracji

Zauważamy, że dla zbioru Iris algorytm już w pierwszej iteracji osiąga prawie maksymalne wyniki. Widzimy też, że nie potrzebuje od więcej niż 2 iteracji aby zbiec. Brak preprocessingu zdaje się być najlepszym wyborem dla tego zbioru.

2.2.2 Badanie pozostałych parametrów (ilość klastrów oraz nstart)

Spodziewanie, dla ilości klastrów równej ilości klas (w tym przypadku 3), wartość miary purity jest najepsza - dla wyższej ilośći klastrów ewidentnie spada. Najlepszym wyborem na parametr nstart jest wartość 10. Jest to także spodziewany wniosek, gdyż im większa ilość początkowo przetestowanych inicjalizacji tym mniejszy wpływ na dobór centroidów ma losowość. Ponownie brak preprocessingu zdaje się być najlepszym wyborem.

Dla miary silhouette natomiast, zauważamy, że spada ona wraz ze wzrostem ilość klastrów, dla dwóch klastrów rezultat jest najepszy. Powodem takiego zachowania prawdopodobnie jest duże podobieństwo pomiędzy klasami Iris-virginica i versicolor co widzieliśmy w procesie wizualizacji.

2.2 PAM

W ramach badanie algorytmu PAM skupimy się na 3 parametrach:

Miary purity oraz silhouette mają podobne trendy jak miało to miejsce dla K-means. Ponownie metody z brakiem standaryzacji zachowuję się lepiej. Metryka manhattan zdaje się być minimalnie lepsza niżeli euclidean.

3 Wnioski

K-means osiągnęło najlepszy wynik na poziomie ok. 0.89 dla miary purity. PAM natomiast ok. 0.9 dla tej samej miary. Wyniki pomiędzy metodami są dosyć zbliżone, jednak wizualnie algorythm PAM zdaje się być bardziej stabilny i odporny na outliery (co widzimy dla zamieszczonej wizualizacji klastrów).

WINE

1. K-means vs PAM (domyślne parametry)

Dla każdej z metod klasteryzacji wykonane zostało 5 prób - w każdej początkowe centroidy są wybierane losowo.

Klastry dla w zasadzie nie różnią się przy wyborze różnych startowych centroidów. Dla K-means natomiast zauważamy inny rozkład klastrów dla 4 próby. Obie metody nie dokonują poprawnej klasteryzacji na prawdziwe klasy. W pokazanej projekcji, klasy 2 i 3 mocno na siebie nachodzą. Prawdopodobnie jest to powód słabych wyników klastrowania.

2. Badanie klasteryzacji dla różnych ustawień parametrów początkowych

2.1 K-means

2.1.1 Badanie maksymalnej ilości iteracji

Tak jak to miało miejsce dla zbioru Iris, K-means potrzebuje tylko 2-3 iteracje aby całkowicie zbiec. Tym razem zauważamy znacząco przewagę normalizacji i standaryzacji danych dla miary purity. Dla silhouette widzimy odwrotny trend, jednak prawdopodobnie powodem takiego zachowania jest właśnie dominowanie jednej z cech, który dominuje miarę podobieństwa dla tej metryki.

2.2.2 Badanie pozostałych parametrów (ilość klastrów oraz nstart)

Tak jak zauważyliśmy wcześniej, zbiór WINE wymaga normalizacji/standaryzacji danych. Wartość nstart jest widocznie lepsza dla wyższych ilości klastrów jednak dla ilości klastrów równej ilości klas 3, różnica jest praktycznie nie zauważalna. Wraz ze wzrostem ilości klastrów zarówno metryka purity jak i silhouette maleją.

2.2 PAM

Dla algorytmu PAM, tak jak dla K-means, widzimy, że normalizacja/standaryzacja danych jest istotna w kontekście dobrej klasteryzacji (metryka purity), natomiast miara silhouette jest nie wymierną metryką, gdy dane nie są zpreprocessowane (powód opisany był w ramach zbioru Iris). Także jak w przypadku K-means, wartości miar spadają wraz ze wzrostem ilości klastrów powyżej ilości klas. Metryka manhattan osiąga minimalnie lepsze rezultaty niż euclidean.

3. Wnioski

Dla tego zbioru K-means osiąga lepsze rezultaty od PAM w kontekście metryki purity: 0.95 do 0.90. Powodem może być widoczne w wizualizacji nakładanie się klastrów, które najwidoczniej lepiej jest reprezentowalne przy użyciu centroidów niżeli medoidów. Dla tego zbioru także ważna była normalizacja/standaryzacja danych.

GLASS

1. K-means vs PAM (domyślne parametry)

Dla każdej z metod klasteryzacji wykonane zostało 5 prób - w każdej początkowe centroidy są wybierane losowo.

Zbiór GLASS ma dwa razy więcej klas niż wcześniej badane zbiory - z tego powodu projekcja na dwie główne składowe zawiera tylko ok. 74% wariancji. Klasy dosyć mocno się na siebie nakładają w kontekście miary co jest powodem dużo gorszych przypasowań klastrów niż widzieliśmy przy poprzednich zbiorach. Ponownie klastry PAM są dosyć podobne przy różnych wyborach początkowych centroidów, natomiast K-means zbiega do różnych ich rozłożeń.

2. Badanie klasteryzacji dla różnych ustawień parametrów początkowych

2.1 K-means

2.1.1 Badanie maksymalnej ilości iteracji

Ponownie algorytm zbiega w przeciągu 2-3 iteracji. Co ciekawe brak normalizacji/standaryzacji daje lepsze wyniki zarówno w kontekście purity jak i silhouette.

2.2.2 Badanie pozostałych parametrów (ilość klastrów oraz nstart)

Na zbiorze WINE, zauważamy dużą poprawę jaką wprowadza zwiększenie parametru nstart - wrażliwość na wybór początkowych centroidów jest wyższa niż miało to miejsce dla wcześniejszych zbiorów. Co ciekawe miara purity dla 5 klastrów ze standaryzacją osiąga dosyć dobre rezultaty. Jest to ciekawe ze względu na to, że zbiór ma 6 klas. Powodem takiego zachowania może być zły balans klas obecny w zbiorze oraz istotne nakładanie się klas. Miara silhouette natomiast, najlepsze rezultaty osiąga dla mniejszych ilości klastrów, a wraz ze wzrostem ich ilości spada.

2.2 PAM

Tak jak K-means, PAM osiąga lepsze rezultaty bez standaryzacji. Co ciekawe, najlepsze wartości purity są widoczne dla ilości klastrów równej 4 przy ilości klas 6.

3. Wnioski

K-means ponownie zachowuje się lepiej od PAM: 0.57 do 0.475 dla miary purity i ilości klastrów równej ilości klas. Dla tego zbioru brak zastosowania standaryzacji daje najlepsze rezultaty.

SEEDS

1. K-means vs PAM (domyślne parametry)

Dla każdej z metod klasteryzacji wykonane zostało 5 prób - w każdej początkowe centroidy są wybierane losowo.

Zbiór SEEDS jest najłatwiej separowalnym zbiorem na klastry ze wszystkich rozważanych. Na dwóch głównych składowych bardzo czysto widać podział i oba algorytmy radzą sobie dosyć dobrze z zadaniem.

2. Badanie klasteryzacji dla różnych ustawień parametrów początkowych

2.1 K-means

2.1.1 Badanie maksymalnej ilości iteracji

Tak jak dla wszystkich badanych zbiorów, ilość iteracji na poziomie 2-3 jest wystarczająca do zbiegnięcia metody. Standaryzacja danych natomiast, osiąga minimalnie lepsze rezultaty od pozostałych form preprocessingu.

2.2.2 Badanie pozostałych parametrów (ilość klastrów oraz nstart)

Trednu purity i silhouette są bardzo zbliżone do tych dla zbiorów WINE oraz IRIS, które także miały 3 klasy. Metoda osiąga najlepsze rezultaty w kontekście purity dla ilości klastrów równej 3. Nie widzimy natomiast dużego wpływu wartości nstart - najwidoczniej wybór początkowych centroidów dla tak łatwego zbioru jak SEEDS jest dosyć łatwy, pojedyczny losowy wybór jest wystarczający.

2.2 PAM

PAM zachowuje się podobnie jak K-means. Standaryzacja daje minimalnie lepsze wyniki oraz dla 3 klastrów miara purity osiąga największą wartość.

3. Wnioski

K-means ponownie jest lepszy od PAM: 0.92 do 0.9 w kontekście miary purity. Zbiór SEEDS jest bardzo łatwym zbiorem do klasteryzacji co widzieliśmy przy projekcji na główne składowe.

Pytania

1. Czy przy grupowaniu potrzebna jest normalizacja/standaryzacja danych?

Odp: Powyżej przedstawione eksperymenty wykazały, że normalizacja i standaryzacja danych mają wpływ na wyniki grupowania. Jednak czasami poprawiają wyniki, a innym razem nie - zależy to od zbioru danych. W teorii, normalizacja czy standaryzacja danych powinny być wskazane dla metod grupowania opartych na mierze odległości (np. PAM), gdyż jedne cechy mogą dominować inne w kontekście tworzenia klastra.

2. Co różni oba algorytmy z punktu widzenia reprezentacji klastra?

Odp: W K-means klaster jest grupowany przy użyciu centroidu (punkt średni), natomiast w PAM przy użyciu medoidu (punkt centralny w klastrze - o minimalnej odległści do pozostałych elemntów w klastrze).

3. Który z algorytmów jest mniej odporny na szum i wartości odstające (ang. outliers)? Dlaczego?

Odp: K-means jest mniej odporny na szum i wartości odstające, gdyż średnia (centroid) jest bardziej wrażliwa na wartości skrajne niż wybór punktu centralnego (medoid).

4. Czy w zadaniu grupowania powinniśmy użyć walidacji krzyżowej?

Odp: Zastosowanie walidacji krzyżowej w procesie grupowania nie ma zbytniego sensu. Z założenia grupować chcemy zbiory danych, dla których nie znamy poprawnych etykiet elementów i naszym zadaniem jest odkrycie zależności w formie klastrów w obrębie zbioru danych - klasyczne uczenie nienadzorowane. Walidacja krzyżowa ma zastosowanie, gdy korzystamy z metod nadzorowanych w celu ewaluacji jakości modelu. Jednak, gdy takowe posiadamy, nie ma zbytnich powodów żebyśmy korzystali z grupowania nienadzorowanego na rzecz klasyfikatorów nadzorowanych.

5. Czy wyniki badanych algorytmów klasteryzacji powinny być powtarzalne i uśredniane?

Odp: Badane algorytmy klasteryzacji opierają się na losowej inicjalizacji początkowych centroidów. W związku z tym, wyniki pomiędzy odpaleniami algorytmów mogą się różnić, zatem wskazane jest powtórzenie metody parę razy w celu oszacowania wartości metryk jakie osiąga metoda - możemy to robić przez uśrednianie.

6. Co mierzą miary klasteryzacji podane w treści zadania?

Odp: Miara purity mierzy "czystość" klastrów, czyli jak dużo elementów w klastrze należy do klasy dominującej w klastrze. Silhouette natomiast, mierzy jak bardzo elementy są podobne do pozostałych elementów w swoich klastrach.

7. Czy podejście aby liczba klastrów i liczba klas była taka sama jest poprawne w kontekście miary Purity?

Odp: Gdy liczba klastrów jest większa niż ilość klas, kilka klastrów będzie posiadać tą samą klasę. W przeciwnym wypadku gdy ilość klastrów jest mniejsza niż ilość klas, istnieją klasy, które nie są przypisane do żadnego z klastrów - chociaż ta sytuacja też może się wydarzyć dla tej samej ilości klastrów jak i większej. Nie są to niepoprawne konfiguracje dla miary purity.